from functools import cache
from heapq import heappop, heappush
from typing import *

from math import inf


class Solution:
    def minimumCost(
        self,
        source: str,
        target: str,
        original: List[str],
        changed: List[str],
        cost: List[int],
    ) -> int:

        def o(a):
            return ord(a) - ord("a")

        def c(a):
            return chr(ord("a") + a)

        n = len(original)

        h = [[inf] * 26 for _ in range(26)]
        for i in range(n):
            a, b = o(original[i]), o(changed[i])
            h[a][b] = min(h[a][b], cost[i])

        mn = [[inf] * 26 for _ in range(26)]

        def f(i):
            q = []
            for j in range(26):
                if h[i][j] != inf:
                    heappush(q, (h[i][j], j))
            while q:
                c, j = heappop(q)
                if mn[i][j] == inf:
                    mn[i][j] = c
                    for k in range(26):
                        if h[j][k] != inf and mn[i][k] == inf:
                            heappush(q, (h[j][k] + c, k))

        for i in range(26):
            f(i)

        ans = 0
        for a, b in zip(source, target):
            if a == b:
                continue
            c = mn[o(a)][o(b)]
            if c == inf:
                return -1
            ans += c

        return ans


s = Solution()
print(
    s.minimumCost(
        source="abcd",
        target="acbe",
        original=["a", "b", "c", "c", "e", "d"],
        changed=["b", "c", "b", "e", "b", "e"],
        cost=[2, 5, 5, 1, 2, 20],
    )
)
